The present invention relates generally to the halftoning, inverse-halftoning, and facsimile transmission of images. More particularly, the present invention relates to a method of and system for rendering an inverse-halftone from a binary image and methods and apparatus for efficiently transmitting halftone images and for recovering the gray scale image transmitted by inverse-halftoning the received halftone image.
Many printing devices are not capable of reproducing gray scale images because they are bi-level. As a result, the binary representation of a gray scale image is a necessity in a wide range of applications such as laser printers, facsimile machines, lithography (newspaper printing), liquid crystal displays and plasma panels. Gray scale images are typically converted to binary images using halftone techniques. Halftoning renders the illusion of various shades of gray by using only two levels, black and white, and can be implemented either digitally (facsimile machines, laser printers) or optically (newspaper printing).
Inverse-halftoning is the method by which an approximation of a gray scale image is reconstructed from a binary, halftone version of the original image. Digital halftoning is the process of transforming an N-bit gray scale image into a 1-bit binary image perceived to contain a gray scale. Digital inverse-halftoning is the reconstruction of a gray scale image from its halftone rendering.
It is desirable to utilize an inverse-halftoning process on a 1-bit image in many applications. In some situations, the only image available is a halftone rendering and, in order to reconstruct a gray scale image of that halftone rendering, an inverse-halftoning method must be utilized. In other cases, the system receiving the image is capable of displaying a binary display (printers, facsimile devices). Situations may also exist in which it is desirable for halftone images to be displayed on multilevel devices. For example, in comparison to laser and dot matrix printers, the dynamic range of CRT displays is large, causing the display of binary images to appear "harsh" or "loud" when viewed. Also the picture quality of binary images when viewed on multilevel devices can be greatly improved. By generating gray scale approximations to the binary images, the level of low pass filtering that must be performed by the eye on the image can be significantly reduced.
Almost all printed materials are produced by using halftone techniques. Recently, many advances in digital scanning devices have occurred, including the introduction of digital duplicating devices. The ability for such devices to process halftone images, including the ability to convert between halftone algorithms, would be highly advantageous. Also the ability to manipulate halftone images is important and extremely useful to the desk top publishing industry. However, elementary image processing operations such as filtering, decimation, interpolation, sharpening, etc., which are routinely implemented on gray scale images, are not easily performed on halftone images. Methods for the processing of binary texts and binary images are known. However, these algorithms are limited to images which are perceived as binary, and are not applicable to high frequency distributions of black and white which produce the illusion of gray.
Some work with the reconstruction of gray scale images from binary images is known, such as in U.S. Pat. No. 3,953,668 to Judice, entitled "Method and Arrangement for Eliminating Flicker Interlaced Ordered Dither images" and U.S. Pat. No. 4,377,821 to Sautter et al., entitled "Arrangement for Providing a Flickerless Order Dither Image for a Video Display." Other prior art methods are disclosed in an article entitled "Display of Dithered Images," by Netravali and Bowen, Proceedings of the SID, Vol. 22, No. 3, pp. 185-190, 181 and "High Quality Multi-Level Image Restoration from Bi-level Image," by Mita, Sugiura and Shimomura, The Sixth International Congress on Advances in Non-Impact Printing Technologies Black and White and Color, Oct. 21-26, pp. 235-236, 1990. However, these known methods range from simple low pass filtering to complicated neural networks. In general, low pass filtering that is sufficient to smooth the impulses found in binary images is also sufficient to blur the sharp features of such images. Therefore, reconstructions of gray scale images from binary images based on low pass filtering either remain grainy, or become visually displeasing because of such blurring. Neural networks require training, and thus may not be optimal over many different halftone techniques. In addition, neural network techniques do not explicitly take advantage of all of the a priori constraints on the gray scale image and power spectrum, or the nature of the halftone mask when its structure is available. Other prior art inverse-halftoning techniques require exact knowledge of the halftone screen used to produce a binary image (see Roetling, U.S. Pat. No. 4,630,125 and Fan, U.S. Pat. No. 5,027,078) or need to estimate the halftone screen. This is a disadvantage since some halftone techniques, such as error diffusion, have no regular halftone screen.
In this application, for the sake of clarity, the following conventions are used. A gray scale or multilevel image is defined as a two-dimensional light intensity function g(i,j), where i,j denote discrete pixel coordinates, and the value of g at any point (i,j) is proportional to the gray level of the image at that point. An 8-bit gray scale is used, providing L=256 possible gray scale levels lying in the interval [O,L-1] where gray level 1=0 is considered black and 1=255 is considered white. A halftone binary or bi-level image is similarly defined, with the exception that it is composed of 1-bit. Therefore, a halftoned image contains only two gray levels [b.sub.0, b.sub.1 ], where b.sub.0 :b.sub.1 may be considered either 0:1 or 0:255, corresponding to black or white. Preceding all reconstructions, it is assumed that an M.times.N pixel, 8-bit gray scale image of real and positive integers has been halftoned onto a M.times.N, 1-bit binary image. As will be described herein, it is a goal of one aspect of the present invention to reproduce estimates of the original M.times.N 8-bit image which are visually acceptable such that edge and flat image regions are accurately reproduced and free from obvious or annoying artifacts, are acceptable for elementary image processing algorithms, and are capable of allowing conversion between halftone methods.
As discussed above, many information display devices are binary in nature. However, most images are continuous. Therefore, the ability to display continuous tone images on binary devices is very useful. However, the problem of displaying continuous images in a binary form has been unresolved for hundreds of years. This problem arises in many forms of media transfer, from graphic arts to facsimile machines. Virtually all printed images in books, magazines, newspapers, etc. are composed in a binary nature. Computer hard copy devices are almost exclusively binary in nature. The process of transforming continuous gray scale information into binary information which is perceived to contain a continuous tone, is called halftoning.
A continuous image is one that can be defined as "natural". It is one which contains indistinguishable transitions from one gray level to the next. A binary image is one that is composed of picture elements that are either black or white. Therefore, the display of a gray scale image on a binary output device requires that the continuous image be quantized into two levels. The binarization algorithm uses as its input the sample g(i,j) and generates the sample b(i,j) =0 or 1 for the binary image. This thresholding decision can be stated as ##EQU1## where g(i,j) is the gray level of a pixel with coordinates (i,j), and t is the threshold value, an element in [O,L-1].
Equation 1 describes two types of thresholding algorithms. The first type are those in which an image is segmented so that it is perceived as binary. The second type are those which distribute binary picture elements so that the resultant image is perceived to be continuous. A thresholded image which is perceived as binary provides very little, if any, information which will be useful for inverse-halftoning. The latter thresholding algorithm describes halftoning. As will be discussed later, a halftone image contains adequate information for forming a reasonable gray scale reconstruction.
Desirable halftone algorithm characteristics include: implementation simplicity; reproduction accuracy for both low frequency (or constant) and high frequency (or edges in fine detail); and the absence of visual artifacts such as low frequency Moire pattern (aliasing) and false quantization contours (artificial boundaries). Essentially, the desired result of the halftoning process is such that the halftone images observed at normal viewing distances of 30-45 centimeters show dot dispersion which is perceived as varying gray levels, while the underlying dot structure remains unnoticed.
Halftoning can be implemented both optically and digitally. When implemented optically, the process is performed in two photographic steps. The original image is photographed through a mesh or grating called a halftone screen, and the binary character of the image is realized using a high contrast photographic material. Digital implementation of the halftone process has been thoroughly discussed in several articles, such as "A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays," by Jarvis, Judice and Ninke, Computer Graphics and Image Processing, Vol. 5., No. 1, pp. 13-40, 1976. A brief review of several prominent halftone methods is provided next. For a complete analysis of halftone techniques, reference is made to the Jarvis et al. article, as well as others which are reported in the literature.
Halftoning methods are based on either point or neighborhood operations according to the number of points from the input gray scale image required to calculate one output point in the output binary image. A point operation refers to any operation where a one-to-one correspondence between input and output exists. The output for a given location is based only on the single input pixel at that location. In the case of digital halftoning, points correspond to pixels. In point algorithms, the halftoning is accomplished by a simple point-wise comparison of the gray scale image against a non-image, usually aperiodic (but not always) array or mask. For every point in the input image, depending on which point value (the gray scale image or the mask) is larger, either a 1 or a 0 is placed respectively at the corresponding location in the binary output image.
Neighborhood methods correspond to a many-to-one operation. The input pixel and the pixels surrounding it are used to determine the output pixel. Halftoning using neighborhood algorithms is not done by a simple point-wise comparison, but usually requires filtering operations that involve a number of points from the input gray scale image in order to calculate one point in the output image. Point operations can be implemented both digitally and optically. However, neighborhood operations are limited to digital applications. In general, point operations are faster than neighborhood operations, but neighborhood operations yield superior results.
At present, given the existing halftoning algorithms, the choice for a specific halftoning algorithm depends on the target device and always requires a trade-off between image quality and speed. Neighborhood halftoning algorithms result in a good image quality (although the image is not completely artifact free), but they are slow and cannot be optically implemented. That leaves point algorithms as the only choice for optical applications such as newspaper printing. Point algorithms are fast and are suitable for all target devices, but the output usually suffers from artifacts such as periodic artifacts and false contours.
The digital halftoning of images with multiple levels, such as gray scale levels, is known in the art. Two major techniques and several other techniques are currently in use. They are globally fixed thresholding, orthographic tone scale creation, electronic screening, ordered dither, error diffusion and blue noise mask thresholding. Each of those techniques is discussed briefly below.
Globally fixed thresholding is a simple point operation in which all gray level image pixels are compared with a fixed constant. If the gray level is greater than the constant, the result is white. If the gray level is equal to or less than the constant, the result is black. While this method preserves the high contrast components, it contains no tone scale information.
Orthographic tone scale creation manipulates a window of binary pixels to form a series of patterns, each of which represents a gray level value. Together, these patterns form a gray scale which, when printed with minimal inter-character spacing, can result in the reproduction of a continuous image. However, the resulting images can be coarse, with a loss of high frequency information.
Electronic screening is a point operation which is analogous to the optical method described above. It is also an extension to the method of globally fixed thresholding. Elements are compared with a threshold resulting in a black or white decision. The threshold, however, is not held constant. Instead, threshold levels are selected in sequential order from a two dimensional matrix defined as the halftone cell threshold set. The set of thresholds and their arrangement within the threshold set determine the properties (dot dispersion, edge and flat region preservation, etc.) of the halftone image.
Ordered dither is a point operation which represents continuous tones with clusters of dots arranged to give darker or lighter patterns. Input values are compared against a fixed sized screen, and dots are added to the dither lattice with increasing gray levels. Ordered dither techniques include white noise, cluster-dot and dispersed-dot. The disadvantages of ordered dither algorithms include loss of most fine detail and the introduction of periodic artifacts. See Digital Halftoning by R. Ulichney, MIT Press, Cambridge, Mass. (1987). See also R. W. Floyd and L. Steinberg, "Adaptive Algorithm for Spatial Gray Scale", SID International Symposium Digest of Technical Papers, pps. 36-37. The Floyd and Steinberg paper is directed to the digital halftoning of a gray scale.
The major ordered dither techniques are the clustered-dot dither and dispersed-dot dither techniques. A white noise random dither technique is seldom utilized because it produces the poorest quality image and, of the other two dither techniques, clustered-dot is by far the most used. Both of those techniques are based upon a threshold screen pattern that is of a fixed size. For example, 6.times.6 threshold screens may be compared with the digital input values. If the input digital value is greater than the screen pattern number, a 1 is produced and, if it is less, a 0 value is assigned. The number of levels that can be represented using either technique depends on the size of the screen. For example, a 6.times.6 screen can produce 36 unique levels.
More levels can be achieved with larger patterns, however, a reduction in the effective resolution occurs because the ability to transition among levels is at a coarser pitch. At the pixel rate of about 300 to 500 per inch, which is the average pixel rate of copiers and laser printers, the pattern artifacts are visible for screen patterns larger than 4.times.4, and, since 16 levels do not provide an adequate precision for typical continuous-tone imagery, a suboptimal resolution is usually obtained.
One solution to such a problem is disclosed by Ulichney in a paper "Dithering with Blue Noise" published in the Proceedings of the IEEE, Vol. 76, No. 1, Jan. 1988. In that article, a method of spatial dithering is described which renders the illusion of continuous-tone pictures on displays that are capable of only producing binary picture elements. The method produces a blue noise pattern (high frequency white noise) from a filter to provide desirable properties for halftoning. More specifically, Ulichney uses perturbed-weight error diffusion methods which when digitally implemented run at a much slower speed (approximately 50 times slower) than is attainable with the present invention.
Error diffusion techniques, such as that disclosed in the Ulichney IEEE article, are fundamentally different from ordered dither techniques in that there is no fixed screen pattern. Rather, a recursive algorithm is used that attempts to correct errors made by representing the continuous signal by binary values.
The error diffusion method described by Ulichney, and others, such as Floyd and Steinberg, also has the disadvantage that it requires scanning, convolution-style calculations and, although it can be implemented for use with copiers, facsimile machines, etc., requires local calculations. It cannot, however, be optically implemented. In addition, all error diffusion techniques, including those described by Ulichney and Floyd and Steinberg, show scanning and start-up artifacts, which are not present in the instant invention. Also, while Ulichney describes a method that produces blue noise, the blue noise patterns produced by the present invention are more isotropic than those produced by Ulichney or other error diffusion methods. Utilizing ordered dither methods produces notably periodic patterns that are even much more obtrusive than those produced by error diffusion methods.
The most recently developed halftone technique involves the use of a blue noise mask. Blue noise is the color name given to high frequency white noise. This method utilizes a point operation using a highly isotropic screen which can be implemented both digitally and optically. The mask is constructed to have unique first and second order properties when used to threshold any gray level. It is aperiodic and is void of low frequency components. The halftone image which results from the use of the blue noise mask technique maintains the quality of neighborhood operations while allowing the speed of point operations. This technique is described in U.S. patent application Ser. No. 622,056 filed Dec. 4, 1990, as referenced in the cross-reference section of this application. Unless otherwise noted, this is the technique that is used to create the halftone images utilized by the present invention.
Typically, in preparation for the application of a halftone algorithm to a gray scale image, several preprocessing steps are implemented on the gray scale image. In the first step, the image tone scale is adjusted. Typically, a histogramming point operation is used to force the gray levels near the upper and lower bounds to their respective limit of 0 or L-1, and to remap the gray values in between over the newly expanded range. This clipping operation is referred to as a "punch" or "snap" step. It adds dynamic range by emphasizing the dark and light regions in a halftone image that would otherwise be "flat".
The second step is sharpening. This operation may optionally be used as a compensation operation, for offsetting the effects of halftoning which tend to unsharpen an image. The sharpening step prevents the loss of fine image detail. The third and final step, applied after the sharpening step is the thresholding method as described above. After the thresholding step is performed, the desired halftone image has been generated. The particular and preferred thresholding method utilized in conjunction with the present invention is the blue noise mask method. The halftone images used in conjunction with the instant application are generated in accordance with the preprocessing steps discussed above, which are also shown in FIG. 7.
It is well known that halftone images require lengthy transmission times in facsimile systems. That is because the halftone images are a "mosaic" of black and white pixels without the redundancy of text and line drawings. The efficient compression of binary halftone images has been studied from different points of view including arithmetic coding (see Langdon and Rissanen, "Compression of Black-White Images," IEEE Trans. Comm., COM-29(6) pp. 858-867, 1981 and Urban "Review of Standards for Electronic Imaging for Facsimile Systems," Jour. Elect. Imaging, 1(1) pp. 5-21, 1992). No one method is yet in widespread use, and these are not optimized specifically for high quality halftone reproductions.